The present invention relates to electronic systems, and more particularly, to digital systems and methods with bitstreams representing coded information with codewords of variable length.
The current rapid expansion of digital communication (speech, video, and data) relies on increasingly economical digital signal processing and efficient transmission and storage. For example, video communication has general functionality as illustrated in FIG. 4a, and increasingly includes a link through the air interface as illustrated in FIG. 4b. Many digital communication systems and standards, such as MPEG, use coding with variable length codewords for coding efficiency. Variable length decoding (VLD) is needed for decoding bitstreams whenever variable length coding (VLC) is used by the encoder for generating the bitstreams. A VLC table typically has entries with three fields (codeword length: length; pattern or information encoded: pattern; and variable length codeword: vlc_code). VLD is to determine the value of the fields (length, pattern) based on the vlc_code value extracted from the bitstream. FIG. 2 illustrates the principle of VLD. To find and decode the next codeword, the decoder looks at the sequence of bits forward from the current bitstream position and finds a match to a possible value of vlc_code. Based on the extracted vlc_code value, the VLD determines (length, pattern) by look up in the VLC table, outputs the value of pattern as the decoded next codeword, and then updates the current decoding position in the bitstream according to the decoded codeword length, and starts to decode the next codeword. The look for the next codeword usually reads a fixed length of bits (e.g., the maximal codeword length, len_max, of the entire VLC table) and then searches for a possible codeword; see FIG. 2.
Normally, a decoder includes several VLDs to handle multiple VLCs because VLC tables are different from table to table, and VLD functions have to be implemented differently according to the contents of the VLC tables. For a decoder implementation this implies large code size (or high gate count for hardware solutions) and long development times. Therefore, there is a demand to have a universal VLD method that is able to deal with any VLC table in order to reduce costs and increase flexibility in decoder design.
Obviously, the simplest way to do universal VLD is with the direct VLD table look up; that is, each possible sequence of len_max bits in the bitstream is an index to a table entry containing the next codeword length and pattern. However, this requires a huge VLD table size: indeed, a table with 2len—max entries. For example, if the maximum codeword size of a VLC table is 16 bits (i.e., len_max=16), such a VLD table would have 64 K entries. This is too expensive in terms of memory size.